<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /* 打家劫舍还是需要用dp的
            dp是一个长度为2的数组，dp[0]表示不偷该节点的最大价值。dp[1]表示偷该节点的最大价值

            终止条件：因为是树形，所以当遍历到空节点是return [0,0]

            遍历顺序：需要用后序遍历，遍历到叶子节点。如果偷当前节点，那么左右叶子节点就一定不能偷，如果不偷叶子节点，
            左右节点是可偷可不偷

            */
            var rob = function (root) {
                function postOrder(root) {
                    if (!root) return [0, 0]
                    let left = postOrder(root.left)
                    let right = postOrder(root.right)
                    let withRoot = root.val + left[0] + right[0]
                    let outRoot = Math.max(left[0], left[1]) + Math.max(right[0], right[1])
                    return [outRoot, withRoot]
                }
                let arr = postOrder(root)
                return Math.max(...arr)
            }
        </script>
    </body>
</html>
